Discrete Signal Processing on Graphs: Sampling Theory

摘要

We propose a sampling theory for signals that are supported on eitherdirected or undirected graphs. The theory follows the same paradigm asclassical sampling theory. We show that perfect recovery is possible for graphsignals bandlimited under the graph Fourier transform. The sampled signalcoefficients form a new graph signal, whose corresponding graph structurepreserves the first-order difference of the original graph signal. For generalgraphs, an optimal sampling operator based on experimentally designed samplingis proposed to guarantee perfect recovery and robustness to noise; for graphswhose graph Fourier transforms are frames with maximal robustness to erasuresas well as for Erd\H{o}s-R\'enyi graphs, random sampling leads to perfectrecovery with high probability. We further establish the connection to thesampling theory of finite discrete-time signal processing and previous work onsignal recovery on graphs. To handle full-band graph signals, we propose agraph filter bank based on sampling theory on graphs. Finally, we apply theproposed sampling theory to semi-supervised classification on online blogs anddigit images, where we achieve similar or better performance with fewer labeledsamples compared to previous work.